#define _CRT_SECURE_NO_WARNINGS
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1


typedef struct Node
{
    int data;           //数据域
    struct Node* pnext; //指针域
} NODE, * PNODE;         //NODE等价于struct Node    PNODE等价于struct Node *


PNODE InitList_NODE()//创建链表
{
	int len; //用来存放有效节点的个数
	int val; //用来临时存放用户输入的结点的值
	//分配了一个不存放有效数据的头结点
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if (NULL == pHead)
	{
		printf("分配失败, 程序终止!\n");
		exit(-1);
	}
	// 定义一个临时结构体指针指向最后一个结点
	PNODE ptail = pHead;
	ptail->pnext = NULL;
	printf("请输入您需要生成的链表节点的个数: len = ");
	scanf("%d", &len);
	for (int i = 0; i < len; ++i)
	{
		printf("请输入第%d个节点的值: ", i + 1);
		scanf("%d", &val);
		//新结点
		PNODE pnew = (PNODE)malloc(sizeof(NODE));
		if (NULL == pnew)
		{
			printf("分配失败, 程序终止!\n");
			exit(-1);
		}
		pnew->data = val;
		pnew->pnext = NULL;
		// 将之前的最后一个结点指向新结点
		ptail->pnext = pnew;
		//再将pTail指向新的最后一个结点
		ptail = pnew;
	}
	return pHead;
}

void traverse_list(PNODE pHead)
{//遍历链表
	//获取第一个结点的地址
	PNODE p = pHead->pnext;
	while (p != NULL)
	{
		printf("%d  ", p->data);
		//将结点的指针域(下一个结点的地址)赋值给p
		p = p->pnext;
	}
	printf("\n");
}


int is_empty(PNODE pHead)
{//判断链表是否为空
	if (pHead->pnext == NULL)
	{
		return OK;
	}
	else
	{
		return ERROR;
	}
}

int length_list(PNODE pHead)
{//求链表长度
	PNODE p = pHead->pnext;
	int len = 0;
	while (p != NULL)
	{
		len++;
		p = p->pnext;
	}
	return len;
}


int delete_list(PNODE pHead, int pos)
{
	int i = 0;
	PNODE p = pHead;
	while (NULL != p->pnext && i < pos - 1)
	{
		++i;
		p = p->pnext;
	}
	if (i > pos - 1 || NULL == p->pnext)
		return ERROR;
	//如果程序能执行到这一行说明p已经指向了第pos-1个结点，并且第pos个节点是存在的
	PNODE q = p->pnext;
	p->pnext = p->pnext->pnext;
	//释放q所指向的节点所占的内存
	free(q);
	//变量的值清空
	q = NULL;
	return OK;
}


int getElem(PNODE pHead, int i)
{//取第i个元素的值
	int j = 1; //定义一个计数器
	PNODE p;
	p = pHead->pnext;
	//p不为空且j还有等于i的时候(如果就是第一个元素那么直接调过循环)
	while (p && j < i)
	{
		j++;
		p = p->pnext;
	}
	if (p == NULL || j > i)
	{
		return ERROR;
	}
	return p->data;
}


//按值查找,并返回所在的位置
int locate(PNODE pHead, int e)
{
	int i = 1;
	PNODE p = pHead->pnext;
	while (p && p->data != e)
	{
		i++;
		p = p->pnext;
	}
	if (p)
	{
		return i;
	}
	else
	{
		return ERROR;
	}
}


//输入一个值插入链表
int Insert_List(PNODE pHead, int i, int e)
{
	PNODE p,q;
	p= (PNODE)malloc(sizeof(NODE));
	p->data = e;
	int j = 0;
	q = pHead;
	while (q && j < i - 1)
	{
		q = q->pnext;
		j++;
	}
	if (!p || j > i - 1)
		return ERROR;
	p->pnext = q->pnext;
	q->pnext = p;
	return OK;
}


//销毁(包括头结点)
void destoryList(PNODE pHead)
{
	PNODE p;
	while (pHead)
	{
		//先移动头指针的指向，再去用释放p所对应的空间
		p = pHead;
		pHead = pHead->pnext;
		free(p);
		p = NULL;
	}
}


//清空
// 链表仍然存在将其置空(头结点和头指针仍然存在)
void cleanList(PNODE pHead)
{
	PNODE p, q; //p用来存储上一个结点，q用来移动指针
	//先移动在释放
	p = pHead->pnext;
	while (p)
	{
		q = p->pnext;
		free(p);
		p = NULL;
		p = q;
	}
	//pHead的指针域要清空
	pHead->pnext = NULL;
}



int main() {
	printf("     请选择对应操作:\n");
	printf("     1:创建并初始化链表 \n");
	printf("     2:遍历链表 \n");
	printf("     3:判断链表是否为空 \n");
	printf("     4:求链表长度 \n");
	printf("     5:删除链表中的值 \n");
	printf("     6:获取链表中的第i个值 \n");
	printf("     7:按值查找,并返回所在的位置 \n");
	printf("     8:输入一个值并插入链表 \n");
	printf("     9:销毁链表 \n");
	printf("     10:清空链表 \n");
	printf("     0:退出链表 \n");
	PNODE Head = NULL;
	while (1)
	{
		int n = 0;//顺序表操作
		int x = 0;//是否退出顺序表
		int i = 0;//判断位置及是否为空,链表长度
		int a = 0;//输入的值
		printf("请选择对应操作:");
		scanf("%d", &n);
		switch (n)
		{
		case 0:
			x = 1;
			break;
		case 1:
			//创建一个非循环单链表，并将该链表的头结点的地址付给Head
			Head = InitList_NODE();
			break;
		case 2:
			traverse_list(Head);
			break;
		case 3:
			i = is_empty(Head);
			if (i == 1)
				printf("该链表为空!\n");
			else
				printf("该链表不为空!\n");
			break;
		case 4:
			//求链表长度
			i = length_list(Head);
			printf("该链表长度为%d\n", i);
			break;
		case 5:
			printf("请输入删除的第i个值:");
			scanf("%d", &a);
			i = delete_list(Head, a);
			if (i == 1)
				printf("删除成功!\n");
			else
				printf("删除数据不在链表中!\n");
			break;
		case 6:
			printf("输入你要查找的第i个值:");
			scanf("%d", &i);
			a=getElem(Head, i);
			if (a)
				printf("第%d个值为%d!\n", i, a);
			else
				printf("该链表中没有第%d个值或者超出链表范围!\n");
			break;
		case 7:
			printf("请输入查找的值:");
			scanf("%d", &a);
			i = locate(Head,a);
			if (i)
				printf("该值在链表中的位置为%d\n", i);
			else
				printf("该值在链表中不存在!\n");
			break;
		case 8:
			printf("请输入插入的值及位置:");
			scanf("%d %d", &a, &i);
			i=Insert_List(Head, i, a);
			if (i)
				printf("插入成功!\n");
			else
				printf("插入位置不合理!\n");
			break;
		case 9:
			//销毁(包括头结点)
			destoryList(Head);
			printf("销毁链表成功!\n");
			break;
		case 10:
			//清空
            // 链表仍然存在将其置空(头结点和头指针仍然存在)
			cleanList(Head);
			printf("该链表已清空!\n");
			break;
		}
		if (x == 1)
		{
			break;
		}
	}
	return 0;
}



